package com.sicheng.algorithm.recursive;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/9/15 21:21
 */
public class ClockArray {


    public static void main(String[] args) {
        ClockArray clockArray = new ClockArray();
        int[][] array = {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
                {13, 14, 15, 16},
        };

        clockArray.clockArray(array);
    }

    /*
    http://www.cyc2018.xyz/%E7%AE%97%E6%B3%95/%E5%89%91%E6%8C%87%20Offer%20%E9%A2%98%E8%A7%A3/29.%20%E9%A1%BA%E6%97%B6%E9%92%88%E6%89%93%E5%8D%B0%E7%9F%A9%E9%98%B5.html#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0
     */

    /**
     * 题目描述
     * 按顺时针的方向，从外到里打印矩阵的值。
     * {
     * {1,  2,  3,  4 },
     * {5,  6,  7,  8 },
     * {9, 10,  11, 12},
     * {13, 14, 15, 16},
     * }
     * 矩阵打印结果为：1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10
     */
    public void clockArray(int[][] array) {
        if (array != null && array.length > 0 && array[0].length > 0) {
            int[][] path = new int[array.length][array.length];
            clockArray(array, 0, 0, path);
        }
    }

    public void clockArray(int[][] array, int i, int j, int[][] path) {

        path[i][j] = 1;
        System.out.print(array[i][j] + " ");
        if (j + 1 < array.length && notPassed(path, i, j + 1)) {
            if (i - 1 >= 0 && notPassed(path, i - 1, j)) {
                clockArray(array, i - 1, j, path);//向右走时若可以向上走，优先向上
            } else
                clockArray(array, i, j + 1, path);//向右走
        }
        if (i + 1 < array.length && notPassed(path, i + 1, j))
            clockArray(array, i + 1, j, path);//向下走
        if (j - 1 >= 0 && notPassed(path, i, j - 1))
            clockArray(array, i, j - 1, path);//向左走
        if (i - 1 >= 0 && notPassed(path, i - 1, j))
            clockArray(array, i - 1, j, path);//向上走

    }

    public boolean notPassed(int[][] path, int i, int j) {
        return path[i][j] != 1;
    }
}

